package com.cuz.daileetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 见 Daileetcode48
 */
public class Day48 {

    /**
     * 每一行升序，每一列升序的二位数组中 查找目标值
     *
     * @param matrix 二维数组
     * @param num    目标寻找数字
     * @return 下标
     */
    static int[] sortedMatrixFind(int[][] matrix, int num) {
        if (matrix == null) {
            return new int[]{-1, -1};
        }
        int row = matrix.length;
        int col = matrix[0].length;
        //首先从右上角的开始找起，下方的数是大于当前数的数，左方的数是小于当前数的数
        for (int rowIndex = 0; rowIndex < row; ) {
            for (int colIndex = 0; colIndex < col; ) {
                //当前位置的数
                int value = matrix[rowIndex][colIndex];
                //相等直接返回
                if (value == num) {
                    return new int[]{rowIndex, colIndex};
                } else if (value < num) {
                    //当前数小于目标 向下
                    rowIndex++;
                } else {
                    //当前数大于目标数 向左
                    colIndex--;
                }
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[][] arr = {{0, 0, 0, 0, 1}, {0, 0, 0, 1, 1}, {0, 0, 1, 1, 1}, {0, 0, 1, 1, 1}, {0, 0,0, 1, 1}};
        System.out.println(mostOneRow(arr));
    }

    /***
     * 一个矩阵只包含0和1 且同一行中0一定在1的左边
     * 找到包含最多1的行号进行返回
     * @param matrix 二位数组
     * @return 最多1的行号集合 可能存在多行
     */
    static List<Integer> mostOneRow(int[][] matrix) {
        ArrayList<Integer> result = new ArrayList<>();
        if (matrix == null) {
            return result;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int colIndex = col - 1;
        //初始化第一行的 数组，最左的一个1的列
        for (; colIndex >= 0; colIndex--) {
            if (matrix[0][colIndex] == 0) {
                break;
            }
        }
        //第一行最左的1的列
        colIndex += 1;
        //把第一行加入
        result.add(0);
        //从第二行开始
        for (int rowIndex = 1; rowIndex < row; rowIndex++) {
            //记录当前行最左1的列
            int tempCol = colIndex;
            //如果和上一最多1的列相同，但是为0说明这一行的1少于最多1的行 那么直接continue
            if (matrix[rowIndex][colIndex] == 0) {
                continue;
            }
            //如果当前位置是1 那么向左 直到找到最右的0
            while (tempCol >= 0 && matrix[rowIndex][tempCol] == 1) {
                tempCol--;
            }
            //最右的0++就是最左的1
            tempCol++;
            //当前行最左的1 比最多1的列小，说明当前行才是最多1的行
            if (tempCol < colIndex) {
                //之前的结果作废
                result.clear();
                //把当前的假如
                result.add(rowIndex);
                //更新最左1的列
                colIndex = tempCol;
            } else if (tempCol == colIndex) {
                //相等 那么假如到结果中 也是 最多1的一行啊
                result.add(rowIndex);
            }
        }
        return result;
    }
}
